package tree.递归;

import po.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 前序遍历构造二叉搜索树1008.java
 * @Description https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/
 * @createTime 2021年08月26日 19:28:00
 */
public class 前序遍历构造二叉搜索树1008 {
	Map<Integer, Integer> inOrderMap = new HashMap<>();

	public TreeNode bstFromPreorder(int[] preorder) {
		int[] inOrder = new int[preorder.length];
		System.arraycopy(preorder, 0, inOrder, 0, preorder.length);
		Arrays.sort(inOrder);
		for (int i = 0; i < inOrder.length; i++) {
			inOrderMap.put(inOrder[i], i);
		}
		//中序遍历： 左子树 【inStart,inRootIndex-1],左子树长度为 inRootIndex-1-inStart ,右子树为[inRootIndex+1,inEnd]
		//前序遍历： 左子树  [preStart+1,preStart+1+左子树长度] 由上面可以得到  左子树为[preStart+1,preStart+1+inRootIndex-1-inStart] =
		// [preStart+1,preStart+inRootIndex-inStart]
		//前序遍历： 右子树  [preStart+1+左子树长度+1 , preEnd] 由上面可以得到  右子树为[preStart+1+inRootIndex-1-inStart+1 , preEnd] =
		// [preStart+inRootIndex-inStart+1 , preEnd]
		return find(0, preorder.length - 1, preorder, 0, preorder.length - 1, inOrder);
	}

	private TreeNode find(int preStart, int preEnd, int[] preorder, int inStart, int inEnd, int[] inOrder) {
		if (preStart > preEnd || inStart > inEnd) {
			return null;
		}
		int rootVal = preorder[preStart];
		TreeNode treeNode = new TreeNode(rootVal);
		Integer rootIndex = inOrderMap.get(rootVal);
		treeNode.left=find(preStart+1,preStart+rootIndex-inStart,preorder,inStart,rootIndex-1,inOrder);
		treeNode.right=find(preStart+rootIndex-inStart+1,preEnd,preorder,rootIndex+1,inEnd,inOrder);
		return treeNode;
	}
}
